1. Field of the Invention
The present invention relates generally to visualizing data points, and in particular, to a method, apparatus, and article of manufacture for normalizing a view of large point cloud data.
2. Description of the Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found below in the section entitled “References.” Each of these publications is incorporated by reference herein.)
Point clouds are often created by reality capture devices such as laser three-dimensional (3D) scanners that measure a large number of points (e.g., from thousands to many billions of points [3D coordinates]) on the surface of an object, and output a point cloud as a data file. The point cloud represents the visible surface of the object that has been scanned or digitized. With the increase usage of such reality capture devices, large point cloud data sets are more frequently created for consumption by design applications. The challenge that design software faces is visualizing and using this data efficiently in the applications. While the point cloud data set is often very large, the number of points an application is capable of handling for visualization and other needs is a small fraction—a few million points, for example. Prior art methods fail to provide the ability to process the massive volume of points, in real time (e.g., preserving a ten [10] frames per second or faster rate) to read a small fraction of points that have the property of accurately representing the original data set without loss of detail or information that causes misrepresentation of the original data. Such problems may be better understood with a detailed description of prior art point cloud processing and viewing methodologies.
Point cloud visualization and applications are increasingly important in design, especially due to the decrease in the price point of the technology. Point clouds can contain an enormous number of points. One of the major challenges is representing the set of points while providing the ability to extract a small subset that is highly representative of the spatial region of interest.
As described above, a point cloud is created using a laser beam/scanner that scans objects/surfaces to obtain millions of points. Prior art methodologies may attempt to select a subset of the points in a quick and efficient manner. One approach divides a volume of interest into equal size rectangular 3D cells. Each of the thousands of cells may contain millions of points. The issue arises as to how to determine how many and which points to select from/in a cell. In the prior art, the total number of points in a cell may be compared to the total number of points in other cells. These relative totals are then used to determine how many points to select from each cell. Thereafter, points are merely read in the order in which they are stored in memory. Point sample density falls off as the square of the distance from the scanner, since the scan process can be viewed as emitting rays radially from the scanner location. Thus, the further an object/surface lies from the optics source, the sparser the sampled points are.
Accordingly, there is a desire to eliminate the scanner artifact, to normalize the point selection, and to obtain a uniform distribution/real depiction of the distribution of the point cloud data regardless of the location of the scanner. Many prior art approaches have attempted to solve such problems. Such approaches range from nearest neighbor based approaches [1] to frequency domain based approaches [4]. Concepts of downsampling, borrowed from image processing techniques have also been incorporated in solutions to view large point data sets [2]. Goals of some techniques include noise removal and optimal representation, at the expense of computation and with freedom to modify the original point set [3].
Another prior art based solution (e.g., AutoCAD™ PCG™ available from the assignee of the present invention) referred to as a point cloud decimation engine (which is described in copending U.S. patent application Ser. No. 12/619,490, filed Nov. 16, 2009, which application is incorporated by reference herein), while maintaining really good frame rates, may have issues with a “halo” effect around the scanners, since the indexing scheme uses the count of points within a cell to determine the relative point contribution from the cell. In this regard, FIGS. 1A and 1B illustrate the halo effect caused by prior art solutions. In FIG. 1A, the “S” indicates the location of the scanner device. As illustrated, an object/surface on a plane (r) close to the scanner S will have more points scanned compared to that of an object laying on a plane (3r) located a further distance from the scanner S. FIG. 1B illustrates a “halo” with a dense pattern of points for the object in close proximity to the scanner/light source.
However, to provide a practical approach, an industrial strength and simple solution is paramount, with a clear demonstration of uniformity of display for a wide class of customer data sets.